An organization having a large number of personnel with similar or different roles typically require rosters to assign individuals to such roles and for different shifts. These rosters need to be optimized according to constraints associated with the individuals or the roles. Traditionally, rostering is performed manually and this requires one or more persons to determine how various tasks and assignments are allocated to appropriate individuals. Persons involve with rostering require knowledge of parameters such as availability and skill levels of each individual in the organization. However, manual rostering has problems that are impossible or tedious to resolve such as when an individual requests for a change of assignment or cannot perform a task because of sickness or lack of requisite skills.
With developments in electronic computing and software, genetic algorithms provide an improved technique to optimize solutions for tasks that deal with various parameters such as scheduling. In genetic algorithms, each gene typically represents one solution parameter and a chromosome has one or more genes that are encoded to represent the various solution parameters. For example, U.S. Pat. No. 5,848,403 Gabriner et al., assigned to BBN Corporation, describes an improved genetic algorithm scheduling system that creates genomes using cost factors and weight settings to produce initial genomes that encode at least partly optimized schedules.
However, rostering is different from the scheduling system described in U.S. Pat. No. 5,848,403 Gabriner et al. In scheduling, the duration of each task is given and resource and temporal constraints are also known. The main objective of scheduling is to find a start time for every task and, typically at the same time, to allocate proper resources for the task as well. Often, the main objective requires total costs to be minimized.
In rostering, an organization needs round-the-clock coverage of tasks and the objective of rostering is to assign specific individuals to take turns performing a list of duties. Such round-the-clock coverage includes organizations such as, for example, health care facilities, service desks of public utility companies, police and fire departments. Before planning, a roster planner must be given parameters such as a roster period, task and shift specifications. A roster generally defines a work sequence using a shift list on a rotating basis within a group based upon the parameters. Thus, rostering relates to shift distribution as well and this is more than just controlling time for performing tasks as required in scheduling. A roster seeks to balance staff within constraints set by the parameters. In some instances, rostering may have to accommodate other constraints due to individual preferences, capability and availability.
Genetic algorithms are used to obtain optimal rostering solutions based upon the principles of natural evolution, which depends substantially on fitness. In a rostering system based upon genetic algorithms, solution of a problem is encoded in a chromosome. Each unit of the chromosome, known as a gene, is a variable with a defined range of values. Genetic algorithms operate on a population of encoded solutions or chromosomes in a selection-reproduction evolution cycle. The first generation of a selection-reproduction evolution cycle consists of a number of randomly generated chromosomes, which are selected according to a fitness quality. Selected fit members of the first generation are put into a mating pool for reproduction from which a new generation is derived by combining (crossover) or altering (mutating) genes among individuals within the population. The selection-reproduction evolution cycle repeats until an optimal solution is found or after a number of predetermined evolution cycles.
Genetic algorithms are useful in solving many real world problems. However, a preliminary condition that leads to a successful application of genetic algorithms is that solution space of the problem being addressed must be encoded using chromosomes with a manageable length. A chromosome is typically denoted using Ck, where k=1 to Z, and Z denotes population size. Each chromosome can have LC genes such that Ck=(gk,1; gk,2; gk,3; gk,4; . . . gk,Lc-1, gk,Lc)
Typically, in modeling genes for existing genetic algorithms systems, a chromosome (Ck) represents a solution and a gene (gk,j, where j=1 to LC) represents an element of that solution. In this modeling, the element can have X values, each value being statically represented by a value of the gene. For example, in a rostering problem, an element of a roster solution can be a shift with variations according to a time period such as a day shift, a night shift or a non-working shift.
There are numerous ways to arrange shifts in a roster period. Applying static gene modeling using genetic algorithms to roster these shifts may not be feasible when the total number of permutations is huge. Consequently, a gene may have a large number of values that dramatically increase a solution space and significantly slow down evolutionary cycles. One solution to this problem is to use predefined shift patterns to store all shift permutations. However, this is not possible as some shifts cannot be pre-defined and the number of shift permutations can still be huge.
Generally, existing rostering systems using genetic algorithms get more complex when the number of solution parameters increases and this increases the length of chromosomes. Computational complexity further increases when these solution parameters have varying values that further increase the solution space. When chromosomes exceed a manageable length in such existing rostering systems, it becomes unfeasible to provide optimal roster solutions.
Therefore, a need clearly exists for a genetic algorithms rostering system, method and product to search for optimal roster solutions in situations with large solution spaces that require lengthy chromosomes that cannot be managed by existing rostering systems.